﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SudokuGame.Sudoku
{
    public class SudokuGenerator
    {
        private const int BoardSize = 9;
        private const int EmptyCellValue = 0;

        private Random random;
        private readonly ChaosRandomEx chaosRandomEx;
        public SudokuGenerator()
        {
            random = new Random();
            chaosRandomEx = new ChaosRandomEx();
        }

        public SudokuCell[,] GenerateSudoku(DifficultyLevel difficulty)
        {
            SudokuCell[,] board = new SudokuCell[BoardSize, BoardSize];

            // 初始化数独网格
            for (int row = 0; row < BoardSize; row++)
            {
                for (int col = 0; col < BoardSize; col++)
                {
                    board[row, col] = new SudokuCell(row, col, EmptyCellValue);
                }
            }

            // 填充数独网格
            FillSudoku(board);

            // 根据难度要求移除部分单元格的值
            RemoveCells(board, difficulty);

            return board;
        }


        private void FillSudoku(SudokuCell[,] board)
        {
            SolveSudoku(board);
        }

        private bool SolveSudoku(SudokuCell[,] board)
        {
            int row = 0;
            int col = 0;

            if (!FindEmptyCell(board, ref row, ref col))
            {
                // 所有单元格都已填满，数独已解决
                return true;
            }

            List<int> numbers = GetRandomNumberSequence();

            foreach (int num in numbers)
            {
                if (IsValidMove(board, row, col, num))
                {
                    // 尝试填充数字
                    board[row, col].Number = num;

                    if (SolveSudoku(board))
                    {
                        // 递归解决剩余的单元格
                        return true;
                    }

                    // 回溯到上一个单元格
                    board[row, col].Number = EmptyCellValue;
                }
            }

            return false;
        }

        private bool FindEmptyCell(SudokuCell[,] board, ref int row, ref int col)
        {
            for (row = 0; row < BoardSize; row++)
            {
                for (col = 0; col < BoardSize; col++)
                {
                    if (board[row, col].Number == EmptyCellValue)
                    {
                        return true;
                    }
                }
            }

            return false;
        }

        public bool IsValidMove(SudokuCell[,] board, int row, int col, int num)
        {
            // 检查行是否合法
            for (int i = 0; i < BoardSize; i++)
            {
                if (board[i, col].Number == num)
                {
                    return false;
                }
            }

            // 检查列是否合法
            for (int i = 0; i < BoardSize; i++)
            {
                if (board[row, i].Number == num)
                {
                    return false;
                }
            }

            // 检查子网格是否合法
            int subgridRow = (row / 3) * 3;
            int subgridCol = (col / 3) * 3;

            for (int i = 0; i < 3; i++)
            {
                for (int j = 0; j < 3; j++)
                {
                    if (board[subgridRow + i, subgridCol + j].Number == num)
                    {
                        return false;
                    }
                }
            }

            return true;
        }

        private List<int> GetRandomNumberSequence()
        {
            List<int> numbers = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
            Shuffle(numbers);
            return numbers;
        }

        private void Shuffle<T>(List<T> list)
        {
            int n = list.Count;
            while (n > 1)
            {
                n--;
                int k = random.Next(n + 1);
                T value = list[k];
                list[k] = list[n];
                list[n] = value;
            }
        }

        private void RemoveCells(SudokuCell[,] board, DifficultyLevel difficulty)
        {
            int cellsToRemove = GetCellsToRemoveCount(difficulty);

            for (int i = 0; i < cellsToRemove; i++)
            {
                int row = random.Next(BoardSize);
                int col = random.Next(BoardSize);

                if (board[row, col].Number != EmptyCellValue)
                {
                    board[row, col].Number = EmptyCellValue;
                }
                else
                {
                    i--;
                }
            }
        }

        private int GetCellsToRemoveCount(DifficultyLevel difficulty)
        {
            return difficulty switch
            {
                DifficultyLevel.Medium => 32,
                DifficultyLevel.Hard => 44,
                DifficultyLevel.VeryHard => 56,
                DifficultyLevel.SuperHard => 68,
                DifficultyLevel.Insane => 80,
                _ => 20
            };
        }
    }
}
